#include <stdio.h>
#include <stdlib.h>
#define maxsize 80
typedef struct BNode
{
    BNode *lchild;
    BNode *rchild;
    int data;
} BNode, *BTree;

typedef struct Queue
{
    int front;
    int rear;
    BNode *node[maxsize];
} Queue;

// 队空条件：q.front = q.rear
// 队满条件：(q.rear + 1) % maxsize = q.front
// 队长度：(q.rear - q.front + maxsize) % maxsize
int getWidth(BTree T)
{
    if (!T)
    {
        return 0;
    }
    
    // 初始化队列
    Queue q;
    q.front = q.rear = 0;

    // 根节点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;

    int width = 1;
    while (q.front != q.rear)
    {
        // 获取队列长度，就代表当前层结点个数
        int num = (q.rear - q.front + maxsize) % maxsize;
        if (num > width)
        {
            width = num;
        }
        
        for (int i = 0; i < num; i++)
        {
            // 出队并访问
            BNode *temp = q.node[q.front];
            q.front = (q.front + 1) % maxsize;

            // 孩子结点入队
            if (temp->lchild)
            {
                q.node[q.rear] = temp->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }

            if (temp->rchild)
            {
                q.node[q.rear] = temp->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
        }
        
    }
    return width;
}

// 测试
BNode *GetNode(int x)
{
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
}

/***
 *          1
 *      3       2
 *   4        6    5
 * */
int main()
{
    BTree T = GetNode(1);
    T->lchild = GetNode(3);
    T->rchild = GetNode(2);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);
    T->rchild->lchild = GetNode(6);

    int width = getWidth(T);
    printf("%d\n", width);
    return 0;
}